package demo.practice.dp;

public class P221 {
    public static void main(String[] args) {
        P221 p221 = new P221();
        p221.maximalSquare(new char[][]{{'0', '0', '0', '1'}, {'1', '1', '0', '1'}, {'1', '1', '1', '1'}, {'0', '1', '1', '1'}, {'0', '1', '1', '1'}});
    }

    public int maximalSquare(char[][] matrix) {

        int h = matrix.length;
        int w = matrix[0].length;
        int dp[][] = new int[h][w];

        //dp[i][j]代表当前位置上 有值的高

        for (int j = 0; j < w; j++) {
            dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
        }
        for (int i = 1; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (matrix[i][j] == '1') {
                    //当前有值
                    dp[i][j] = dp[i - 1][j] + 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        int maxAre = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (dp[i][j] == 0) {
                    continue;
                }
                //矩形的宽度
                int sw = 1;
                int sh = dp[i][j];
                for (int k = j - 1; k >= 0; k--) {
                    //向右边扩展
                    if (dp[i][k] >= dp[i][j]) {
                        sw++;
                    } else {
                        break;
                    }
                }

                for (int k = j + 1; k < w; k++) {
                    //向右边扩展
                    if (dp[i][k] >= dp[i][j]) {
                        sw++;
                    } else {
                        break;
                    }
                }

                maxAre = Math.max(maxAre, sw > sh ? sh * sh : sw * sw);
            }
        }
        return maxAre;
    }
}
